# LeetCode 264、丑数II(动态规划)
# 一、题目描述
我们把只包含质因子 2、3 和 5 的数称作丑数(Ugly Number)。求按从小到大的顺序的第 n 个丑数。
示例:
输入: n = 10 输出: 12 解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
说明:
1
是丑数。n
不超过1690。
# 二、题目解析
对于任意一个丑数来说,它都可以和 2、3、5 进行相乘得到一个丑, 那么每个丑数都可以得到三个数,这三个数分别属于不同的数组中。
假设当前已经知道丑数序列 nums 是这些元素:1, 2, 3, 4, 5, 6, 8, 9
。
1、nums2 数组存储了这个序列中所有丑数与 2 相乘的结果,nums2 = { 1 * 2 , 2 * 2 ,3 * 2 , 4 * 2 ,5 * 2 ,6 * 2 ,8 * 2,。。。}
2、nums3 数组存储了这个序列中所有丑数与 3 相乘的结果,nums3 = { 1 * 3 , 2 * 3 ,3 * 3 , 4 * 3 ,5 * 3 ,6 * 3 ,8 * 3,。。。}
3、nums5 数组存储了这个序列中所有丑数与 5 相乘的结果,nums5 = { 1 * 5 , 2 * 5 ,3 * 5 , 4 * 5 ,5 * 5 ,6 * 5 ,8 * 5,。。。}
那么,想填充 nums 的话,它的选择来源肯定只能来源于 nums2 、nums3、nums5 这三个数组。
并且 nums 序列接下来填充的数是 nums2 、nums3、nums5 这三个数组除去已经在 nums 序列的丑数时剩下的最小值。
也就是说,每次寻找丑数的过程是在 nums2 、nums3、nums5 这三个数组中寻找最小值的过程。
- 1、在寻找过程中,因为丑数的序列在不断的扩充,nums2 、nums3、nums5 这三个数组也在不断的扩充。
- 2、每次找到那个最小值之后,接下来的寻找过程应该忽略它了。
那么,现在来看 nums2 、nums3、nums5 这三个数组的起始状态,此时,丑数序列只有一个元素 ugly[0] = 1
。
- nums2 :{1 * 2......}
- nums3: {1 * 3......}
- nums5 :{1 * 5......}
第二个丑数序列需要去获取 nums2 、nums3、nums5 这三个数组的第一个元素的最小值。
那么,此时可以设置三个索引,分别指向 nums2、nums3、nums5 数组开始的位置。
- index2 指向 nums2 数组
- index3 指向 nums3 数组
- index5 指向 nums5 数组
比较的结果是发现 1 * 2 最小,于是第二个丑数找到了,此时 ugly 就变成 { 1 , 2 } ,nums2 、nums3、nums5 这三个数组也需要得到扩充。
- nums2 :{1 * 2 ,2 * 2 ,......}
- nums3: {1 * 3, 2 * 3 ,......}
- nums5 :{1 * 5, 2 * 5 ,......}
刚才我们说过,每次找到那个最小值之后,接下来的寻找过程应该忽略它了,用代码的形式来表示就是索引值向后移动。
比如在 nums2 上找到了 1 * 2 之后,index2 开始移动到 2 * 2 的位置。
第三个丑数序列需要去获取 nums2 、nums3、nums5 这三个数组中 index2、index3、index5 指向元素的最小值。
- index2 指向了 nums2 中的 2 * 2,即 nums2[index2]
- index3 指向了 nums3 中的 1 * 3,即 nums3[index3]
- index5 指向了 nums5 中的 1 * 5,即 nums5[index5]
如此不断的循环,就可以把 ugly 数组填充到 n 的位置,得到 ugly[n]。
这里需要注意到, nums2 、nums3、nums5 这三个数组并没有具体的额外创造出来,它们都在 ugly 数组中。
- nums2 实际上就是 ugly[]*2 的结果
- nums3 实际上就是 ugly[]*3 的结果
- nums5 实际上就是 ugly[]*5 的结果
所以比较的过程,实际上就是比较 nums2[index2] = ugly[index2] * 2
、 nums3[index3] = ugly[index3] * 3
、 nums5[index5] = ugly[index5] * 5
三者大小的过程,获取到最小值就填充到 ugly 数组中,再将对应的索引向后移动,由于 nums2 、nums3、nums5 这三个数组中会存在重复元素,所以需要执行去重的操作。
# 三、参考代码
# 1、Java 代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者:程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
class Solution {
public int nthUglyNumber(int n) {
// 设置一个数组,用来存放结果
// nums[0] 表示第 1 个丑数,结果是 1
// nums[1] 表示第 2 个丑数,结果是 2
// nums[n-1] 表示第 n 个丑数,结果需要计算
int[] nums = new int[n];
// nums[0] 表示第 1 个丑数,结果是 1
nums[0] = 1;
// 对于任意一个丑数来说,它总是可以由前面的丑数与 2、3、5 其中一个进行相乘而来的
// 那么每个丑数都可以得到三个数,这三个数分别属于不同的数组中
// nums2 = {1*2, 2*2, 3*2, 4*2, 5*2, 6*2, 8*2...}
// nums3 = {1*3, 2*3, 3*3, 4*3, 5*3, 6*3, 8*3...}
// nums5 = {1*5, 2*5, 3*5, 4*5, 5*5, 6*5, 8*5...}
// nums2 按照从小到大的顺序存放了所有丑数和 2 相乘的结果
// nums3 按照从小到大的顺序存放了所有丑数和 3 相乘的结果
// nums5 按照从小到大的顺序存放了所有丑数和 5 相乘的结果
// nums[i] 的值就是在这三个数组中进行挑选
// 设置三个索引,分别指向 nums2、nums3、nums5 数组开始的位置
// 每当 nums[i] 的值从哪个数组中获取到,该索引就在这个数组中向后移动
// index2 指向 nums2 数组
int index2 = 0;
// index3 指向 nums3 数组
int index3 = 0;
// index5 指向 nums5 数组
int index5 = 0;
// 开始填充 nums 数组
for (int i = 1; i < n; i++) {
// nums[i] 的值就是在这三个数组中进行挑选最小值
// 但是,这三个数组并没有具体的额外创造出来,它们都在 nums 数组中
// 其中 nums[index2] 表示的就是第 index2 个丑数,nums[index2] * 2 在数组 nums2 中的位置为 index2
// 其中 nums[index3] 表示的就是第 index3 个丑数,nums[index3] * 3 在数组 nums3 中的位置为 index3
// 其中 nums[index5] 表示的就是第 index5 个丑数,nums[index5] * 5 在数组 nums5 中的位置为 index5
nums[i] = Math.min(Math.min(nums[index2] * 2, nums[index3] * 3), nums[index5] * 5);
// 执行完上面的代码之后,nums[i] 已经被填充完毕
// 那么和它相等的数需要被挪出接下来的比较
// nums[i] == nums[index2] * 2
// 移动 index2 到下一个数
if (nums[i] == nums[index2] * 2) {
index2++;
}
// nums[i] == nums[index3] * 3
// 移动 index3 到下一个数
if (nums[i] == nums[index3] * 3) {
index3++;
}
// nums[i] == nums[index5] * 5
// 移动 index5 到下一个数
if (nums[i] == nums[index5] * 5) {
index5++;
}
}
// 返回结果
return nums[n - 1];
}
}
# 四、复杂度分析
- 时间复杂度 O(N) : 其中 N = n ,有个 for 循环,需遍历列表。
- 空间复杂度 O(N) : 创造了长度为 N 的结果数组,需要使用 O(N)的额外空间。